/*
https://leetcode-cn.com/problems/count-different-palindromic-subsequences/solution/tong-ji-bu-tong-hui-wen-zi-zi-fu-chuan-by-leetcode/
 */
public class Solution730 {
    public int countPalindromicSubsequences(String s) {
        int mod=1000000007;
        int[][][] dp=new int[4][s.length()][s.length()];
        for (int i=s.length()-1;i>=0;i--){
            for (int j=i;j<s.length();j++){
                for (int k=0;k<4;k++){
                    char c=(char)(k+'a');
                    if (i==j){
                        if (c==s.charAt(i)){
                            dp[k][i][j]=1;
                        }else {
                            dp[k][i][j]=0;
                        }
                    }else {
                        if (s.charAt(i)!=c){
                            dp[k][i][j]=dp[k][i+1][j];
                        }else if (s.charAt(j)!=c){
                            dp[k][i][j]=dp[k][i][j-1];
                        }else {
                            dp[k][i][j]=2;
                            for (int t=0;t<4;t++){
                                dp[k][i][j]=(dp[k][i][j]+dp[t][i+1][j-1])%mod;
                            }
                        }
                    }
                }
            }
        }
        int ans=0;
        for (int t=0;t<4;t++){
            ans=(ans+dp[t][0][s.length()-1])%mod;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution730().countPalindromicSubsequences("abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"));
    }
}
